#表示从i到j两点之间的最近路径距离，i到j若无边则为最近路径上边的加和
inf = float('inf')
c_i_j = [
    [0,5,21,13,6,15,12,20],
    [5,0,16,18,7,12,19,17],
    [21,16,0,33,16,7,17,11],
    [13,18,33,0,17,26,16,29],
    [6,7,16,17,0,9,12,14],
    [15,12,7,26,9,0,10,5],
    [18,19,17,16,12,10,0,13],
    [20,17,11,29,14,5,13,0]
]

'''(状态压缩)动态规划(DP)算法'''
N = len(c_i_j)
M = 1 << (N - 1) #用二进制各位表示子集的状态（即状态压缩）,
                 # 集合S最大为，除城市0外，城市1至N-1均在S表示的集合中,因此为2^(N-1)


#dp_distance保存从起点1经子集j到i停止的最短距离
dp_distance = [[0 for j in range(M)] for i in range(N)]
#保存路径，最后输出结果
path = []

#核心函数，求动态规划dp_distance数组
def TSP():
    #初始化dp_distance[i][0](即从i出发直接返回初始点0)
    for i in range(N):
        dp_distance[i][0] = c_i_j[i][0]
    #求解dp_distance[i][j],先更新列，再更新行
    for j in range(1,M):
        for i in range(N):
            dp_distance[i][j] = inf #初始化为无穷大
            if i == 0:
                pass
            else:
                #如果子集合j中包含结点i（j二进制与i对应位为1），直接跳过求解
                if (j >> (i - 1))&1 == 1:
                    continue
            for k in range(1,N):
                if (j >> (k - 1))&1 != 1: #如果集合中没有节点k，跳过
                    continue
                if dp_distance[i][j] > c_i_j[i][k] + dp_distance[k][j ^ (1<<(k-1))]: #用异或过滤掉K点
                    dp_distance[i][j] = c_i_j[i][k] + dp_distance[k][j ^ (1<<(k-1))]

#判断节点是否都已访问，不包含出发点0
def is_visited(visited_list):
    for i in range(1,N):
        if not visited_list[i]:
            return False
    return True

#获取最优路径，保存在path中
def getpath():
    visited_list = [0]*N
    pioneer,min,S = 0,inf,M-1
    temp = 0
    
    path.append(0)  #初始节点0作为路径起点
    while not is_visited(visited_list):
        for i in range(1,N):
            if visited_list[i] == 0 and S&(1<<(i-1)) != 0:
                if min > c_i_j[i][pioneer] + dp_distance[i][S^(1<<(i-1))]:
                    min = c_i_j[i][pioneer] + dp_distance[i][S^(1<<(i-1))]
                    temp = i
        pioneer = temp
        path.append(pioneer)
        visited_list[pioneer] = 1
        S = S ^ (1<<(pioneer - 1))
        min = inf
    path.append(0)

if __name__ == "__main__":
    TSP()
    #print(dp_distance)
    print("最小值为：",dp_distance[0][M-1])
    getpath()
    print("最优路径为：",path)

            

